#![allow(dead_code)]
use std::{
    cell::RefCell,
    cmp,
    cmp::Reverse,
    collections::{BinaryHeap, HashMap, HashSet, VecDeque},
    fmt::Display,
    hash::{Hash, Hasher},
    rc::Rc,
};

#[derive(Debug, Clone)]
struct RefVec<T>(Rc<RefCell<Vec<T>>>);
impl<T> RefVec<T> {
    fn new(v: Vec<T>) -> Self {
        Self(Rc::new(RefCell::new(v)))
    }
}
impl<T> PartialEq for RefVec<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0.as_ptr() == other.0.as_ptr()
    }
}
impl<T> Eq for RefVec<T> {}

struct RefSet<T>(Rc<RefCell<HashSet<RefNode<T>>>>);
impl<T> RefSet<T> {
    fn new(s: RefNode<T>) -> Self {
        let mut set = HashSet::new();
        set.insert(s);
        Self(Rc::new(RefCell::new(set)))
    }
}
impl<T> PartialEq for RefSet<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0.as_ptr() == other.0.as_ptr()
    }
}
impl<T> Eq for RefSet<T> {}

#[derive(Debug, Clone)]
struct RefNode<T>(Rc<RefCell<Node<T>>>);
impl<T> Hash for RefNode<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        (self.0.as_ptr()).hash(state)
    }
}
impl<T> PartialEq for RefNode<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0.as_ptr() == other.0.as_ptr()
    }
}
impl<T> RefNode<T> {
    fn new(elem: T) -> Self {
        Self(Rc::new(RefCell::new(Node::new(elem))))
    }
}
impl<T> Eq for RefNode<T> {}

#[derive(Debug)]
struct RefEdge<T>(Rc<RefCell<Edge<T>>>);
impl<T> Hash for RefEdge<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        (self.0.as_ptr()).hash(state)
    }
}
impl<T> PartialEq for RefEdge<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0.as_ptr() == other.0.as_ptr()
    }
}
impl<T> Eq for RefEdge<T> {}
impl<T> PartialOrd for RefEdge<T> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.0.borrow().weight.cmp(&other.0.borrow().weight))
    }
}
impl<T> Ord for RefEdge<T> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.0.borrow().weight.cmp(&other.0.borrow().weight)
    }
}
impl<T> RefEdge<T> {
    fn new(edge: Edge<T>) -> Self {
        Self(Rc::new(RefCell::new(edge)))
    }
}

#[derive(Debug)]
struct Graph<T> {
    nodes: HashMap<T, RefNode<T>>, // 点集
    edges: Vec<RefEdge<T>>,        // 边集
}
impl<T> Graph<T> {
    fn new() -> Self {
        Self {
            nodes: HashMap::new(),
            edges: Vec::new(),
        }
    }
}

#[derive(Debug)]
struct Edge<T> {
    weight: i32,
    from: RefNode<T>,
    to: RefNode<T>,
}
impl<T> Ord for Edge<T> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.weight.cmp(&other.weight)
    }
}
impl<T> PartialOrd for Edge<T> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
impl<T> PartialEq for Edge<T> {
    fn eq(&self, other: &Self) -> bool {
        self.weight == other.weight
            && self.from.0.as_ptr() == other.from.0.as_ptr()
            && self.to.0.as_ptr() == other.to.0.as_ptr()
    }
}
impl<T> Edge<T> {
    fn new(weight: i32, from: RefNode<T>, to: RefNode<T>) -> Self {
        Self { weight, from, to }
    }
}
impl<T> Eq for Edge<T> {}

#[derive(Debug)]
struct Node<T> {
    elem: T,                // 节点数据
    in_degree: i32,         // 入度，有多少节点指向它
    out_degree: i32,        // 出度，它指向多少节点
    nexts: Vec<RefNode<T>>, // 它指向的节点
    edges: Vec<RefEdge<T>>, // 它的边
}
impl<T> PartialEq for Node<T> {
    fn eq(&self, other: &Self) -> bool {
        (self as *const Self) == (other as *const Self)
    }
}
impl<T> Eq for Node<T> {}
impl<T> Hash for Node<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        (self as *const Self).hash(state)
    }
}

impl<T> Node<T> {
    fn new(elem: T) -> Self {
        Self {
            elem,
            in_degree: 0,
            out_degree: 0,
            nexts: vec![],
            edges: vec![],
        }
    }
}

fn create_graph<T: Hash + Eq + Display + Copy>(matrix: Vec<(i32, T, T)>) -> Graph<T> {
    let mut graph = Graph::new();
    for node_info in matrix.iter() {
        let weight = node_info.0;
        let from = node_info.1;
        let to = node_info.2;
        // 将from, to 两个节点加入图中
        graph.nodes.entry(from).or_insert(RefNode::new(from));
        graph.nodes.entry(to).or_insert(RefNode::new(to));
        // 新建一条边(weight, from, to)
        let edge = RefEdge::new(Edge::new(
            weight,
            RefNode(
                graph
                    .nodes
                    .get(&from)
                    .expect(format!("未发现{}号节点", from).as_str())
                    .0
                    .clone(),
            ),
            RefNode(
                graph
                    .nodes
                    .get(&to)
                    .expect(format!("未发现{}号节点", to).as_str())
                    .0
                    .clone(),
            ),
        ));
        /* 更新to节点：to.in ++ */
        graph
            .nodes
            .entry(to)
            .and_modify(|node| node.0.borrow_mut().in_degree += 1);

        /* 更新from节点:
        1. from.nexts.add(to_node)
        2. from.out++
        3. from.edges.add(edge)
        */
        let to_node = graph.nodes.get(&to).unwrap().0.clone();
        graph.nodes.entry(from).and_modify(|node| {
            node.0.borrow_mut().out_degree += 1;
            node.0.borrow_mut().nexts.push(RefNode(to_node));
            node.0.borrow_mut().edges.push(RefEdge(edge.0.clone()));
        });
        graph.edges.push(edge);
    }

    graph
}

fn bfs<T>(node: RefNode<T>) -> Vec<T>
where
    T: Hash + Eq + Display + Copy,
{
    let mut res: Vec<T> = vec![];
    let mut queue: VecDeque<RefNode<T>> = VecDeque::new();
    let mut set: HashSet<RefNode<T>> = HashSet::new();
    res.push(node.0.borrow().elem);
    queue.push_back(node);
    while let Some(node) = queue.pop_front() {
        for node_next in node.0.borrow().nexts.iter() {
            if !set.contains(node_next) {
                res.push(node_next.0.borrow().elem);
                queue.push_back(RefNode(node_next.0.clone()));
                set.insert(RefNode(node_next.0.clone()));
            }
        }
    }

    res
}

fn dfs<T>(root: RefNode<T>) -> Vec<T>
where
    T: Hash + Eq + Display + Copy,
{
    let mut stack: Vec<RefNode<T>> = vec![];
    let mut res: Vec<T> = vec![];
    let mut set: HashSet<RefNode<T>> = HashSet::new();
    res.push(root.0.borrow().elem);
    stack.push(root);
    while let Some(node) = stack.pop() {
        for next in node.0.borrow().nexts.iter() {
            if !set.contains(next) {
                res.push(next.0.borrow().elem);
                stack.push(RefNode(node.0.clone()));
                stack.push(RefNode(next.0.clone()));
                set.insert(RefNode(next.0.clone()));
                break;
            }
        }
    }
    res
}

fn sorted_topology<T>(graph: &Graph<T>) -> Vec<T>
where
    T: Hash + Eq + Display + Copy,
{
    // {node: in}
    let mut map: HashMap<RefNode<T>, i32> = HashMap::new();
    let mut zero_in: VecDeque<RefNode<T>> = VecDeque::new();
    let mut res: Vec<T> = vec![];

    for node in graph.nodes.values() {
        map.insert(node.clone(), node.0.borrow().in_degree);
        if node.0.borrow().in_degree == 0 {
            zero_in.push_back(node.clone());
        }
    }
    while let Some(node) = zero_in.pop_back() {
        res.push(node.0.borrow().elem);
        for next in node.0.borrow().nexts.iter() {
            map.entry(next.clone()).and_modify(|in_degree| {
                *in_degree -= 1;
                if *in_degree == 0 {
                    zero_in.push_back(next.clone());
                }
            });
        }
    }
    res
}

struct UnionFindSet<T> {
    set: HashMap<RefNode<T>, RefSet<T>>,
}
impl<T: Display> UnionFindSet<T> {
    fn new(nodes: Vec<RefNode<T>>) -> Self {
        let mut set = HashMap::new();
        for node in nodes.iter() {
            set.insert(
                RefNode(node.0.clone()),
                RefSet::new(RefNode(node.0.clone())),
            );
        }
        Self { set }
    }

    fn is_same_set(&self, from: RefNode<T>, to: RefNode<T>) -> bool {
        if self.set.get(&from).is_none() || self.set.get(&to).is_none() {
            return false;
        }

        let from_set = self.set.get(&from).unwrap();
        let to_set = self.set.get(&to).unwrap();
        from_set == to_set
    }

    fn union_set(&mut self, from: RefNode<T>, to: RefNode<T>) {
        let mut union_set = HashSet::new();
        {
            let from_set = self.set.get(&from).unwrap().0.borrow();
            for node in from_set.iter() {
                union_set.insert(RefNode(node.0.clone()));
            }
            let to_set = self.set.get(&to).unwrap().0.borrow();
            for node in to_set.iter() {
                union_set.insert(RefNode(node.0.clone()));
            }
        }
        let union_set = RefSet(Rc::new(RefCell::new(union_set)));
        for node in union_set.0.borrow().iter() {
            self.set
                .entry(RefNode(node.0.clone()))
                .and_modify(|set| *set = RefSet(union_set.0.clone()));
        }
    }
}

fn kruskal_mst<T: Display>(graph: &Graph<T>) -> Vec<RefEdge<T>> {
    let mut nodes: Vec<RefNode<T>> = vec![];
    let mut min_heap = BinaryHeap::new();
    let mut min_heap2 = BinaryHeap::new();
    let mut res: Vec<RefEdge<T>> = vec![];

    graph
        .nodes
        .values()
        .for_each(|node| nodes.push(RefNode(node.0.clone())));
    let mut union_find = UnionFindSet::new(nodes);

    for edge in graph.edges.iter() {
        min_heap.push(Reverse(RefEdge(edge.0.clone())));
    }

    graph
        .edges
        .iter()
        .for_each(|edge| min_heap2.push(Reverse(RefEdge(edge.0.clone()))));

    while let Some(Reverse(edge)) = min_heap.pop() {
        if !union_find.is_same_set(
            RefNode(edge.0.borrow().from.0.clone()),
            RefNode(edge.0.borrow().to.0.clone()),
        ) {
            res.push(RefEdge(edge.0.clone()));
            union_find.union_set(
                RefNode(edge.0.borrow().from.0.clone()),
                RefNode(edge.0.borrow().to.0.clone()),
            );
        }
    }

    res
}

fn prime_mst<T>(graph: &Graph<T>) -> Vec<RefEdge<T>> {
    let mut set: HashSet<RefNode<T>> = HashSet::new();
    let mut min_heap: BinaryHeap<Reverse<RefEdge<T>>> = BinaryHeap::new();
    let mut res: Vec<RefEdge<T>> = vec![];

    for node in graph.nodes.values() {
        set.insert(RefNode(node.0.clone()));
        node.0
            .borrow()
            .edges
            .iter()
            .for_each(|edge| min_heap.push(Reverse(RefEdge(edge.0.clone()))));

        while let Some(Reverse(min_edge)) = min_heap.pop() {
            let to_node = RefNode(min_edge.0.borrow().to.0.clone());
            if !set.contains(&to_node) {
                res.push(RefEdge(min_edge.0.clone()));
                to_node
                    .0
                    .borrow()
                    .edges
                    .iter()
                    .for_each(|edge| min_heap.push(Reverse(RefEdge(edge.0.clone()))));
                set.insert(to_node);
            }
        }
    }
    res
}

struct DijData<T> {
    weight: i32,
    road: Vec<RefEdge<T>>,
}
impl<T> DijData<T> {
    fn new(weight: i32) -> Self {
        Self {
            weight,
            road: vec![],
        }
    }
}

fn get_min_w<T>(
    weight_map: &HashMap<RefNode<T>, i32>,
    set: &HashSet<RefNode<T>>,
) -> Option<RefNode<T>> {
    let mut min_w = i32::MAX;
    let mut res = None;
    weight_map.iter().for_each(|(node, &weight)| {
        if !set.contains(node) && weight < min_w {
            min_w = weight;
            res = Some(RefNode(node.0.clone()));
        }
    });
    res
}

fn update<T>(distance_map: &mut HashMap<RefNode<T>, i32>, node: &RefNode<T>) {
    let distance = *distance_map.get(node).unwrap();
    node.0.borrow().edges.iter().for_each(|edge| {
        distance_map
            .entry(RefNode(edge.0.borrow().to.0.clone()))
            .and_modify(|w| *w = cmp::min(*w, distance + edge.0.borrow().weight));
    });
}

fn dijkstra<T: Copy>(graph: &Graph<T>, start: &RefNode<T>) -> Vec<(T, i32)> {
    let mut cloked: HashSet<RefNode<T>> = HashSet::new();
    let mut distance_map: HashMap<RefNode<T>, i32> = HashMap::new();
    graph.nodes.values().for_each(|node| {
        distance_map.insert(RefNode(node.0.clone()), i32::MAX);
    });
    distance_map
        .entry(RefNode(start.0.clone()))
        .and_modify(|w| *w = 0);

    while let Some(min_w_node) = get_min_w(&distance_map, &cloked) {
        if !cloked.contains(&min_w_node) {
            update(&mut distance_map, &min_w_node);
            cloked.insert(min_w_node);
        }
    }

    let mut res: Vec<(T, i32)> = vec![];
    distance_map.iter().for_each(|(node, weight)| {
        res.push((node.0.borrow().elem, *weight));
    });
    res
}

pub fn test_graph() {
    let matrix: Vec<(i32, i32, i32)> = vec![
        (5, 11, 12),
        (6, 11, 21),
        (7, 12, 13),
        (1, 12, 22),
        (1, 13, 14),
        (1, 13, 23),
        (1, 14, 24),
        (1, 21, 22),
        (1, 21, 31),
        (1, 22, 23),
        (1, 22, 32),
        (1, 23, 24),
        (1, 23, 33),
        (1, 24, 34),
        (1, 31, 32),
        (1, 31, 41),
        (1, 32, 33),
        (1, 32, 42),
        (1, 33, 34),
        (1, 33, 43),
        (1, 34, 44),
        (1, 41, 42),
        (1, 42, 43),
        (1, 43, 44),
    ];
    let graph: Graph<i32> = create_graph::<i32>(matrix);
    let node = RefNode(graph.nodes.get(&11).expect("没有结点11").0.clone());
    let res = bfs(node.clone());
    println!("广度优先搜索结果：{:?}", res);
    let res = dfs(node.clone());
    println!("深度优先搜索结果：{:?}", res);

    let matrix: Vec<(i32, char, char)> = vec![
        (1, 'A', 'B'),
        (1, 'A', 'C'),
        (1, 'A', 'D'),
        (1, 'B', 'C'),
        (1, 'B', 'E'),
    ];
    let graph: Graph<char> = create_graph(matrix);
    let res = sorted_topology(&graph);
    println!("res: {:?}", res);

    let matrix: Vec<(i32, char, char)> = vec![
        (3, 'A', 'B'),
        (3, 'B', 'A'),
        (7, 'A', 'D'),
        (7, 'D', 'A'),
        (100, 'A', 'C'),
        (100, 'C', 'A'),
        (5, 'B', 'C'),
        (5, 'C', 'B'),
        (2, 'B', 'D'),
        (2, 'D', 'B'),
        (1000, 'C', 'D'),
        (1000, 'D', 'C'),
    ];
    println!("matrix: {:?}", matrix);
    let graph: Graph<char> = create_graph(matrix);
    let res = kruskal_mst(&graph);
    println!("[kruskal算法] 最小连通图：");
    for edge in res.iter() {
        println!(
            "边：({}, [{}] -> [{}])",
            edge.0.borrow().weight,
            edge.0.borrow().from.0.borrow().elem,
            edge.0.borrow().to.0.borrow().elem
        );
    }
    println!("");

    let res = prime_mst(&graph);
    println!("[prime算法] 最小连通图：");
    res.iter().for_each(|edge| {
        println!(
            "边：({}, [{}] -> [{}])",
            edge.0.borrow().weight,
            edge.0.borrow().from.0.borrow().elem,
            edge.0.borrow().to.0.borrow().elem
        )
    });
    println!("");

    let matrix: Vec<(i32, char, char)> = vec![
        (1, 'A', 'C'),
        (1, 'C', 'A'),
        (6, 'A', 'B'),
        (6, 'B', 'A'),
        (5, 'A', 'D'),
        (5, 'D', 'A'),
        (5, 'B', 'C'),
        (5, 'C', 'B'),
        (3, 'B', 'E'),
        (3, 'E', 'B'),
        (5, 'C', 'D'),
        (5, 'D', 'C'),
        (4, 'C', 'F'),
        (4, 'F', 'C'),
        (2, 'D', 'F'),
        (2, 'F', 'D'),
        (6, 'E', 'F'),
        (6, 'F', 'E'),
    ];
    println!("matrix: {:?}", matrix);
    let graph: Graph<char> = create_graph(matrix);
    let res = kruskal_mst(&graph);
    println!("[kruskal算法] 最小连通图：");
    res.iter().for_each(|edge| {
        println!(
            "边：({}, [{}] -> [{}])",
            edge.0.borrow().weight,
            edge.0.borrow().from.0.borrow().elem,
            edge.0.borrow().to.0.borrow().elem
        )
    });
    println!("");

    let res = prime_mst(&graph);
    println!("[prime算法] 最小连通图：");
    res.iter().for_each(|edge| {
        println!(
            "边：({}, [{}] -> [{}])",
            edge.0.borrow().weight,
            edge.0.borrow().from.0.borrow().elem,
            edge.0.borrow().to.0.borrow().elem
        )
    });
    println!("");

    println!("=========单元最短距离===========");
    let matrix: Vec<(i32, char, char)> = vec![
        (3, 'A', 'B'),
        (3, 'B', 'A'),
        (15, 'A', 'C'),
        (15, 'C', 'A'),
        (9, 'A', 'D'),
        (9, 'D', 'A'),
        (2, 'B', 'C'),
        (2, 'C', 'B'),
        (200, 'B', 'E'),
        (200, 'E', 'B'),
        (7, 'C', 'D'),
        (7, 'D', 'C'),
        (14, 'C', 'E'),
        (14, 'E', 'C'),
        (16, 'D', 'E'),
        (16, 'E', 'D'),
    ];
    let graph: Graph<char> = create_graph(matrix);
    let start = graph.nodes.get(&'A').unwrap();
    let res = dijkstra(&graph, start);
    println!("最小距离：{:?}", res);
}
